package leetcode.leetcode_hot100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class T0399 {


    /**
     * 最短路径算法（Floyd算法）
     */
    class Solution2 {
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int nvars = 0;
            Map<String, Integer> variables = new HashMap<>();

            int n = equations.size();
            for (int i = 0; i < n; i++) {
                if (!variables.containsKey(equations.get(i).get(0))) {
                    variables.put(equations.get(i).get(0), nvars++);
                }
                if (!variables.containsKey(equations.get(i).get(1))) {
                    variables.put(equations.get(i).get(1), nvars++);
                }
            }
            double[][] graph = new double[nvars][nvars];
            for (int i = 0; i < nvars; i++) {
                Arrays.fill(graph[i], -1.0);
            }
            for (int i = 0; i < n; i++) {
                int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
                graph[va][vb] = values[i];
                graph[vb][va] = 1.0 / values[i];
            }
            //Floyd算法
            for (int k = 0; k < nvars; k++) {
                for (int i = 0; i < nvars; i++) {
                    for (int j = 0; j < nvars; j++) {
                        if (graph[i][k] > 0 && graph[k][j] > 0) {
                            graph[i][j] = graph[i][k] * graph[k][j];
                        }
                    }
                }
            }

            int queriesCount = queries.size();
            double[] ret = new double[queriesCount];
            for (int i = 0; i < queriesCount; i++) {
                List<String> query = queries.get(i);
                double result = -1.0;
                if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
                    int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));
                    if (graph[ia][ib] > 0) {
                        result = graph[ia][ib];
                    }
                }
                ret[i] = result;
            }
            return ret;
        }
    }

    /**
     * 带权并查集
     */
    class Solution3 {
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int nvars = 0;
            Map<String, Integer> variables = new HashMap<String, Integer>();

            int n = equations.size();
            for (int i = 0; i < n; i++) {
                if (!variables.containsKey(equations.get(i).get(0))) {
                    variables.put(equations.get(i).get(0), nvars++);
                }
                if (!variables.containsKey(equations.get(i).get(1))) {
                    variables.put(equations.get(i).get(1), nvars++);
                }
            }
            int[] f = new int[nvars];
            double[] w = new double[nvars];
            Arrays.fill(w, 1.0);
            for (int i = 0; i < nvars; i++) {
                f[i] = i;
            }

            for (int i = 0; i < n; i++) {
                int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
                merge(f, w, va, vb, values[i]);
            }
            int queriesCount = queries.size();
            double[] ret = new double[queriesCount];
            for (int i = 0; i < queriesCount; i++) {
                List<String> query = queries.get(i);
                double result = -1.0;
                if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
                    int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));
                    int fa = findf(f, w, ia), fb = findf(f, w, ib);
                    if (fa == fb) {
                        result = w[ia] / w[ib];
                    }
                }
                ret[i] = result;
            }
            return ret;
        }

        public void merge(int[] f, double[] w, int x, int y, double val) {
            int fx = findf(f, w, x);
            int fy = findf(f, w, y);
            f[fx] = fy;
            //可以应用为带权并查集的关键所在
            //除了更新father之外，还需要更新权值
            w[fx] = val * w[y] / w[x];
        }

        public int findf(int[] f, double[] w, int x) {
            if (f[x] != x) {
                int father = findf(f, w, f[x]);
                w[x] = w[x] * w[f[x]];
                f[x] = father;
            }
            return f[x];
        }
    }
}
